In storage devices for computer systems, a digital stream of data modulates the operation of a write transducer (e.g., the current in a coil or intensity of a laser beam) in order to write a series of transitions onto the surface of a rotating magnetic or optical disk in the form of concentric or spiral data tracks. Reading the recorded data entails positioning a read transducer over a data track, sensing the surface transitions, and demodulating the resulting analog read signal into an estimated data sequence representing the originally recorded data.
This process of recording and reading data to and from a disk storage medium is similar to a communication channel where digital data is transmitted through a noisy communication medium such as a cable or the atmosphere. In both communication and recording systems, the goal is to receive/read the transmitted/recorded data reliably and efficiently. Reliability is a measure of how accurate the data is received or, alternatively, the bit error rate in the estimated data sequence detected from the channel signal after having been corrupted by noise inherent in the recording/communication process. Efficiency is a measure of the source data rate; that is, how fast the source data can be transmitted through the communication medium and still maintain a specified bit error rate. In computer storage systems, efficiency is a measure of the linear data density in a given track and the number of concentric tracks per inch (tpi).
In what is known as the "noisy channel coding theorem", Shannon showed that the reliability and efficiency parameters of a communication system are related: the basic limitation that noise causes in a communication channel is not on the reliability of the communication, but on the speed of communication. The maximum rate that data can be transmitted over a discrete-memoryless channel and still make the error probability approach zero is called the channel capacity which is ultimately a function of the channel bandwidth and the signal-to-noise ratio or SNR.
A well known method for increasing the SNR in a communication system, and therefore increase the reliability and efficiency of the system, is to encode the source data according to an error correction code (ECC). Error correction codes increase the effective SNR by increasing the system's immunity to noise. Block error correcting codes are commonly employed in disk storage systems, particularly the Reed-Solomon block code due to its excellent error correction properties and low implementation cost and complexity.
Block codes encode a k-symbol input block of the source data stream into an n-symbol output block or codeword where n-k is the number of redundancy symbols and k/n is referred to as the code rate. The codewords are then transmitted through (stored to) the communication medium and decoded by the receiver. The encoding process performs a mathematical operation over the input block such that the output codewords are different from one another by a parameter referred to as the minimum distance of the code d.sub.min. The minimum distance d.sub.min between codewords determines the amount of noise that the system can tolerate before a received codeword is decoded erroneously.
With Reed-Solomon codes, each symbol of the data stream is typically selected from a finite field GF(2.sup.w) where w is the number of binary data bits in a symbol. Each symbol of the k-symbol input block represents the coefficients of a data polynomial D(x). The redundancy symbols (which are also represented as a polynomial W(x)) are then computed as the modulo division of the input data polynomial D(x) by a generator polynomial G(x): EQU W(x)=(x.sup.m .cndot.D(x)) MOD G(x)
where m is the degree of the generator polynomial which equals the number of redundancy symbols. The redundancy polynomial W(x) is then added to the data polynomial D(x) to generate a codeword polynomial C(x):
ti C(x)=(x.sup.m .cndot.D(x))+W(x).
The encoder circuitry for performing the above operations can be implemented simply as a linear feedback shift register (LFSR).
After encoding, the codeword C(x) is transmitted through the noisy communication channel, wherein the received codeword C'(x) equals the transmitted codeword C(x) plus an error polynomial E(x). The received codeword C'(x) is corrected according to the following steps: (1) compute error syndromes S.sub.i ; (2) compute the coefficients of an error locator polynomial using the error syndromes S.sub.i ; (3) compute the roots of the error locator polynomial, the logs of the roots are the error locations L.sub.i ; (4) compute the error values using the error syndromes S.sub.i and the roots of the error locator polynomial.
The error syndromes S.sub.i are computed as the modulo division of the received codeword polynomial C'(x) by the factors of the generator polynomial G(x): EQU S.sub.i =C'(x) MOD (x+.alpha..sup.i)
when ##EQU1## where .alpha. is a primitive element of the finite field GF(2.sup.w). Techniques for performing the other steps of the decoding process, computing the error locator polynomial, computing the roots of the error locator polynomial, and computing the error values, are well known by those skilled in the art and are not necessary to understand the present invention. See, for example, the above referenced U.S. Pat. No. 5,446,743 entitled "COEFFICIENT UPDATING METHOD AND APPARATUS FOR REED-SOLOMON DECODER."
Another technique known in the prior art to further increase the error tolerance of the system is to arrange the codewords into what is known as a multi-dimensional or product code. Optical disk storage systems, for example, commonly employ a two-dimensional product code as shown in FIG. 2. The codewords are arranged into intersecting horizontal (or row) and vertical (or column) codewords and the decoding process is carried out in iterative passes. First a pass over the horizontal codewords is performed to correct as many errors as possible; any uncorrectable horizontal codewords are left unmodified. Then a pass is made over the vertical codewords to correct as many errors as possible, where a symbol corrected in a vertical codeword also corrects the corresponding symbol for the intersecting horizontal codeword. Consequently, the horizontal codeword may be correctable during the next horizontal pass. Similarly, a symbol corrected during a horizontal pass may render a previously uncorrectable vertical codeword correctable during the next vertical pass. This iterative process continues until the entire product code is corrected, or deemed uncorrectable.
Although the multi-dimensional aspect of a product code significantly increases the error tolerance, the iterative passes over the horizontal and vertical codewords requires a significant amount of compute time. In an optical disk storage device, this compute time translates into latency in reading data from the disk and may also prevent transferring the data on-the-fly in a continuous stream. This can be highly undesirable, especially in multi-media applications which require smooth, uninterrupted audio/video streaming. The above referenced U.S. patent application entitled "A METHOD AND APPARATUS FOR EFFICIENTLY PROCESSING A MULTI-DIMENSIONAL CODE" discloses a method for reducing the processing time of a product code by processing only the horizontal and vertical codewords that have been flagged as containing errors (i.e., error free codewords are skipped). Still, there is a significant latency in reading the codewords from the data buffer in order to regenerate the error syndromes during each of the horizontal and vertical passes.
There is, therefore, a need for a faster, more efficient error correction processor for decoding a multi-dimensional code.